package com.wangpos.datastructure.algorithm

import android.os.Build.VERSION_CODES.N
import kotlin.math.max
import android.icu.lang.UCharacter.GraphemeClusterBreak.V


/**
 * 动态规划算法，是解决多阶段决策问题常用的最优化理论
 *
 *
 * 1. 定义最优子问题
 *
 * 2. 定义状态
 *
 * 3. 定义决策和状态转换方程
 *
 * 4. 确定边界条件
 *
 * 01 背包问题，用动态规划法
 *
 * 给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。
 *
 * 应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
 *
 * 分析一波，面对每个物品，我们只有选择拿取或者不拿两种选择，不能选择装入某物品的一部分，也不能装入同一物品多次。
 *
 * 声明一个 大小为  m[n][c] 的二维数组，m[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为  j 时所能获得的最大价值
 *
 * 那么我们可以很容易分析得出 m[i][j] 的计算方法，
 *
 * 1）. j < w[i] 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿 所以价值还是和上次，只不过容量变大了，但也是当前背包容量的最大值
 * （这个当前容量最大值得意思，只对当前放的这个些物品来讲，比如后面有价值更大的，我们不在本次考虑范围，本次考虑就是放当前物品时背包的最大价值，
 *   同理，当放入第二件物品时，我们就考虑两件物品时当前背包的最大值，我们会一次把所有情况，按照放入物品数量的增加，和背包容量的增加，一次获取最大价值
 * ）
 *  m[ i ][ j ] = m[ i-1 ][ j ]  （m[i-1][j]表示容量增加了，但是不拿物品的价值，对应表正的上一行数据，也是之前算好了）
 *
 *
 *  2）. j>=w[i] 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。

如果拿取，m[ i ][ j ]= m[ i-1 ][ j-w[ i ] ] + v[ i ]。

注意这里解释一下，当前物品数量和背包容量对应的最大值 = 没放入该物品前数量和没放入物品前的容量的最大值 + 当前物品价值

（所以没放入物品前数量对应i-1,
而容量对应j-w[i]，就是当前可以容纳容量j减去当前要放入物品的容量，二对一这个值，在前面的求解当中已经求解，所以，我们就能推倒新的解 ）

这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品，背包容量为j-w[i]时的最大价值，也是相当于为第i件物品腾出了w[i]的空间。

如果不拿，m[ i ][ j ] = m[ i-1 ][ j ]

究竟是拿还是不拿，自然是比较这两种情况那种价值最大。

注意，当我们拿第二件物品的时候，通过这个算法是存在替换的第一件物品的情况，之前一直不理解，以为很顺序有关，第一件放进去了，就一直在里面，后面的累加，实际不是这样

m[ i-1 ][ j-w[ i ] ] 就是会根据当前容量去寻找没装前的容量的最大值 然后再加上自身的价值在去进行补缴

 *
 *
 *
 * 价值数组v = {8, 10, 6, 3, 7, 2}，

重量数组w = {4, 6, 2, 2, 5, 1}，

背包容量C = 12 时对应的m[i][j]数组

 */

/**
 * 注意，我们再数组前添加一个零，这样我们就可以从第一个处理了，第一个处理的实际是第二个数据
 */
fun main(arg: Array<String>) {
    var N = 15

    var v = arrayOf(0, 8, 10, 6, 3, 7, 2)
    var w = arrayOf(0, 4, 6, 2, 2, 5, 1)

    var n = 7
    var c = 13

    var m = Array(7) { IntArray(13) }

    dynamicBag(w, v, n, c, m)

    // 1 2 3

}

/**
 * 　k) 到此，01背包问题已经解决，利用动态规划解决此问题的效率即是填写此张表的效率，
 * 所以动态规划的时间效率为O(number*capacity)=O(n*c)，由于用到二维数组存储子问题的解，所以动态规划的空间效率为O(n*c)；
 */

fun dynamicBag(w: Array<Int>, v: Array<Int>, n: Int, c: Int, m: Array<IntArray>) {

    for (i in 1 until n) {
        for (j in 1 until c) {
            if (j >= w[i]) {
                m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i])
            } else {
                m[i][j] = m[i - 1][j];
            }
        }
    }


    for (i in 1 until n) {
        for (j in 1 until c) {
            print(" ${m[i][j]} ")
        }
        println()
    }

    var x = arrayOf(0, 0, 0, 0, 0, 0, 0)

    println("查找哪些放入背包了")
    findData(x, w, v, n - 1, c - 1, m)

    for (i in 0 until x.size) {
        if (x[i] == 1) {
            println(i)
        }
    }
}

/**
 * 另起一个 x[ ] 数组，x[i]=0表示不拿，x[i]=1表示拿。

m[n][c]为最优值，如果m[n][c]=m[n-1][c] ,说明有没有第n件物品都一样，则x[n]=0 ;
否则 x[n]=1。当x[n]=0时，由x[n-1][c]继续构造最优解；
当x[n]=1时，则由x[n-1][c-w[i]]继续构造最优解。以此类推，可构造出所有的最优解。
 *
 */

fun findData(x: Array<Int>, w: Array<Int>, v: Array<Int>, n: Int, c: Int, m: Array<IntArray>) {
    if (n >= 1) {
        if (m[n][c] == m[n - 1][c]) {
            x[n] = 0
            findData(x, w, v, n - 1, c, m)
        } else if (c - w[n] >= 0 && m[n][c] == m[n - 1][c - w[n]] + v[n]) {
            x[n] = 1
            findData(x, w, v, n - 1, c - w[n], m)
        }
    }
}
